The invention relates generally to the area of computer graphics. It more particularly relates to the use of Coons patches to represent surfaces and the preparation of these patches prior to the rendering of a raster image.
Computer graphics have become an integral part of many people""s lives. The use of graphics in computers has risen dramatically since the use of graphical interfaces for both operating systems and the programs that run on them became commonplace. The incorporation of more detailed graphics has also been a major factor in the rapid increase in memory capacity and processing power in the computer industry. The increased use of graphics and more powerful computing resources have also increased the expectations of the end user. Computer generated graphics must be of high quality with little if any noticeable degradation of image compared to the xe2x80x98real thingxe2x80x99. These demands for high quality graphics have penetrated all levels of computing. This places great demands on the computer systems that are running these graphics intensive programs.
An integral step in the production and manipulation of computer graphics is rendering. In this step an image is often converted into polygons with linear line segments for edges. When the image is in this form the edges of the polygon can be manipulated numerically and the image is altered on the display. However, rendering of an image is not always straight forward. The image should be prepared for rendering such that it appears that same after it is rendered.
Surfaces in a graphics image are often represented by a mesh of surface xe2x80x98patchesxe2x80x99. A Coons patch can be used for this representation. A Coons patch is a specialization of a bicubic (Bezier) patch that is bounded by four arbitrary curves.
An nth-order Bezier curve is defined parametrically by the following equation: where p1 are the control points.       σ    ⁢          (      t      )        =            ∑      1      n        ⁢          xe2x80x83        ⁢                  ρ        i            ⁢              (                              n            !                                              i              !                        ⁢                                          (                                  n                  -                  i                                )                            !                                      )            ⁢                        (                                    t              xe2x80x2                        ⁢                          (                              1                -                t                            )                                )                xe2x80x2            
A Coons patch is a mapping of points in a unit square in (u,v) co-ordinate space, FIG. 1(a), to a patch in (x,y) co-ordinate space, FIG. 1(b). The patch in (x,y) co-ordinate space is bounded by four cubic Bezier curves; c1, c2, d1 and d2. Line 100 (FIG. 1(a)) is a line of constant-u while line 110 is a line of constant-v. The (v=0) and (v=1) edges of the unit square map to curves c1 and c2, respectively. Similarly the (u=0) and (u=1) edges map to curves d1 and d2, respectively. Following the notation used in documentation of Adobe Postscript Coons patch fills (Smooth Shading, Adobe Technical Note #5600, Oct. 10, 1997, Adobe Systems Incorporated), the mapping from a point (u,v) to a point (x,y) equals
S(u,v)=(Sx(u,v), Sy(u,v)) 
and is given by the equations
Sc(u,v)=(1xe2x88x92v)*c1(u)+(v)*c2(u) 
Sd(u,v)=(1xe2x88x92u)*d1(v)+(u)*d2(v) 
Sb(u,v)=(1xe2x88x92v)*[(1xe2x88x92v)c1(0)+(u)*c1(1)]+(1xe2x88x92v)*[(1xe2x88x92u)c1(0)+(u)*c2(1)]
S=Sc+Sdxe2x88x92Sb 
Surfaces patches are used to represent the shape, shading and colours of surfaces. The surface whose shape these patches are representing will quite likely have some contouring. This may take the form of slight waves in the surface or it may take the form of folds.
A Coons patch may contain regions that contain folds which will cause one part of the patch to lie on top of the other. A fold is defined as a region in (x,y) co-ordinate space in which multiple points in (u,v) co-ordinate space map to the same point in (x,y) space. Two Coons patches that contain folds are shown in FIG. 2. The fold in FIG. 2(a) is created by a loop (200) in the patch edge curve while the fold in FIG. 2(b) is created by the edge bending back on itself.
Because a fold maps several points from one co-ordinate space to a single point in another co-ordinate space there may be errors in point priority. Point priority is defined as follows. Assume points (u1,v1) and (u2,v2) in (u,v) co-ordinate space map to the same point in (x,y) co-ordinate space. The point (u1,v1) has a higher priority than point (u2,v2) if v3 greater than v1 or if v2=v1 and u2 greater than u1. While the presence of folds gives Coons patches a 3-D appearance it is not a 3-D surface as the point priority is determined by a 2-D quantity. The mapping of points associated with a fold can cause point priority errors during rendering that will result in a noticeable reduction in image quality. Regions that do not contain folds are referred to as a flat.
A Coons patch can also used to represent the colours of a surface. A colour is assigned to each of the corners of the unit square in (u,v) co-ordinate space and colours inside the square are calculated by bilinear interpolation of the corner colours. The colour of a point in (x,y) space is then determined by the colour at the (u,v) point mapped to it. When multiple points in (u,v) space map to a single point in (x,y) space the colour of that point in (x,y) space is taken to be the colour of the (u,v) source point having the highest priority.
These are several methods that have been used to prepare a Coons patch for rendering. The patch can be subdivided along curves of constant-u and constant-v. This method is illustrated in FIG. 3. These lines in (u,v) co-ordinate space map to Bezier curves in (x,y) co-ordinate space. The sub-patches are also Coons patches. Colours at the new corner points of the sub-patches are calculated from the original patch colours by bilinear interpolation in (u,v) co-ordinate space. Patch subdivision is terminated when the patch shape and colour meet some linearity criteria across the patch and/or when the sub-patch size, as measured by its bounding rectangle, falls below a given threshold. This threshold is typically a small multiple of the dimensions of a raster image pixel. The sub-patches can then be approximated as quadrilaterals and rendered with Gouraud shading (i.e. bilinear colour interpolation). This method is computationally intensive as the resultant sub-patches, which are converted to polygons for rendering are very small.
A method of rendering bicubic patches using Coons patch approximations was disclosed in U.S. Pat. No. 5,063,375 of Lien et. al., issued on Nov. 5, 1991. Multiple single-pixel-wide Bezier curves are drawn to render the surface. The curves are drawn close enough to one another that there are no gaps between them. Each curve is drawn with the v-co-ordinate fixed. The v-co-ordinate is stepped from zero to one with the step size determined dynamically to ensure that are no gaps between the curves. For each curve the endpoint colours are determined by interpolation between corner colours. Pixel colours along the curve are then interpolated between the endpoint colours according to the u-value at each point along the curve.
Goel et.al. disclose a method for rendering surfaces using Bezier patches in U.S. Pat. No. 5,995,109 issued on Nov. 30, 1999. The proposed method is able to render patches with contours but it does not discuss the presence of folds in the patches. The patch is first tested for flatness. If the patch is flat it is divided into triangles for rendering. If the patch is not found to be flat i.e. the patch normal deviates from vertical by more than a prescribed amount, it is divided into sub-patches. The testing and division is continued until the sub-patches are considered to be flat. Once the patches are found to have the desired surface quality they are converted into sets of triangles for which xe2x80x9cestablished rendering hardware existsxe2x80x9d.
The rendering of a Coons patch that contains fold involves considerable computational effort. This computation is associated with the subdivision of the Coons patch or part of a Coons patch containing folds. It is also associated with maintaining point priorities throughout. This is not the case for flat patches. Therefore there is a need to reduce the computation associated with rendering Coons patches that contain folds. A reduction in the computation effort will improve performance.
The invention discloses a method for preparing Coons patches for rendering. The Coons patch is examined for folds and any regions containing folds are isolated from regions that do not contain folds. The rendering method appropriate for fold containing and non-fold containing regions can then be selected. The rendering method appropriate for fold containing regions requires extensive computation compared to that for non-fold containing regions. By isolating the regions containing folds, the invention allows the avoidance of the extensive computation for the non-fold containing regions. Thus, the invention enables reduction of the amount of computation that is required during rendering.
In accordance with an embodiment of the invention a system for preparing a Coons patch having one or more folds, within one or more regions of the Coons patch, that are created by the shape of the edges of the Coons patch for rendering to a raster image is provided. The system comprises; means for determining the location of the one or more regions of the Coons patch that include one or more folds, means for isolating said one or more regions of the Coons patch that includes one or more folds from those regions of the Coons patch that do not include folds, means for subdividing said one or more regions of the Coons patch that include one or more folds, and means for subdividing those regions of the Coons patch that do not include folds.
In accordance with another embodiment of the invention a method for preparing a Coons patch having one or more folds, within one or more regions of the Coons patch, that are created by the shape of the edges of the Coons patch for rendering to a raster image is provided. The method comprises the steps of: determining the location of the one or more regions of the Coons patch that include one or more folds, isolating said one or more regions of the Coons patch that include one or more folds from those regions of the Coons patch that do not include folds, subdividing said one or more regions of the Coons patch that include one or more folds, and subdividing those regions of the Coons patch that do not include folds.
In accordance with another embodiment of the invention a method for determining the location of folds in a Coons patch which has edge curves that are defined by a parametric equation wherein two edges are parallel to lines of constant-v and two edges are parallel to lines of constant-u and the Coons patch is located in u,v co-ordinate space is provided. The method comprises the steps of; determining the derivative of the parametric equation that defines the edge curves of the Coons patch having folds, determining the endpoints of the portion of the edge curve which includes one or more folds, determining the location of points on the edge curve where the derivative of the parametric equation is equal to zero, and comparing the location of points of the edge curve where the derivative of the parametric equation is zero, the endpoints of the portion of the edge curve that includes one or more folds and the endpoints of the edge curve with analogous points of curves known to create folds.
In accordance with another embodiment of the invention a method of isolating the regions of a Coons patch that includes folds from the regions of the Coons patch that do not include folds wherein the Coons patch has two edges that are parallel to lines of constant-v and two edges that are parallel to lines of constant-u wherein u and v define the co-ordinate space is provided. The method comprises the steps of; determining the endpoints of the portion of the edge which includes one or more folds, expanding the range of u-values that define the endpoints of the portion of the edge curve which includes one or more folds and dividing the Coons patch along lines of constant-u such that the regions of the Coons patch that includes folds are isolated from the regions of the Coons patch that do not include folds.
In accordance with another embodiment of the invention a method for rendering a Coons patch having edge curves is provided. The method comprising the steps of; determining presence of a fold on a first edge curve, when a fold is found, isolating a fluid containing region of the Coons patch containing the fold from a non-fold containing region of the Coons patch containing no fold, rendering the fold containing region using a first method which is capable of rendering the fold, and rendering the non-fold containing region using a second method which is simpler than the first method.
Other aspects and advantages of the invention, as well as the structure and operation of various embodiments of the invention, will become apparent to those ordinarily skilled in the art upon review of the following description of the invention in conjunction with the accompanying drawings.